* O prima rezolvare utilizeaza programarea dinamica: 
-se noteaza best[i] - lungimea maxima a unui subsir crescator care se termina pe pozitia i 
- recurenta: best[i] = 1 + max(best[j]) cu 1 ? j < i si a[j] < a[i] 
- pentru a reconstrui solutia mai retinem un vector cu semnificatia:
	pre[i] - pozitia valorii care preceda elementul i in subsirul crescator care se termina pe pozitia i

* Complexitatea optima este O(N*log2N). La fiecare pas i trebuie determinata lungimea cea mai mare best[j] 
unde 1 ? j < i astfel incat aj ? ai
- pentru a afla aceasta informatie in timp optim O(log2N) se poate folosi un arbore de intervale 
sau un arbore indexat binar

- pe scurt trebuie sa facem inca un vector ajutator pentru B cu elementele lui A 
- il vom sorta pe A si vom afla prin cautare binara pe ce pozitie e elementul B in A, pozitie notata cu P[i]
- se va face un Arbore (Int sau Aib) in care se mentine maximul din intervalul i, P[i]
- vecotorul Best se poate construi folosind Query pentru Beg=P[i],End=P[i]

Code:

#include <fstream>
using namespace std;

ifstream F("scmax.in");
ofstream G("scmax.out");

#define Nmax 10000
#define first v
#define second p

int N;
int A[Nmax+11];
int B[Nmax+11];
int P[Nmax+11];
int Arb[Nmax*4+11];

int Pos,Beg,End,Val,Max;

void Update(int,int,int);
void Query(int,int,int);

int Find(int val,int A[])
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] <= val)
           i += step;
    return i;
}

int main()
{
	F>>N;
	
	for (int i=1;i<=N;++i)
		F>>B[i],A[i]=B[i];
	sort(A,A+N+1);
	
	for (int i=1;i<=N;++i)
		P[i]=Find(B[i],A);
	
	for (int i=1;i<=N;++i)
	{
		Beg=1,End=P[i],Max=0;
		Query(1,1,N);
		
		Val=Max+1;Pos=P[i];
		Update(1,1,N);
	}
	
	/*for (int i=1;i<=N;++i)
	{
		Beg=P[i],End=P[i],Max=0;
		Query(1,1,N);
		Best[i]=Max;
	}*/ // asa se scot valorile intr-un vecotor daca e nevoie
	
	Beg=1,End=N;
	Query(1,1,N);
	G<<Max<<'\n';
}

void Update(int Nod,int St,int Dr)
{
	if ( St==Dr )
	{
		Arb[Nod]=Val;
		return;
	}
	
	int Mid=(St+Dr)/2;
	if ( Pos<=Mid )
		Update(2*Nod,St,Mid);
	else
		Update(2*Nod+1,Mid+1,Dr);
	
	Arb[Nod]=max(Arb[2*Nod],Arb[2*Nod+1]);
}

void Query(int Nod,int St,int Dr)
{
	if ( Beg<=St && Dr<=End )
	{
		Max=max(Max,Arb[Nod]);
		return;
	}
	
	int Mid= (St+Dr) /2; 
	if ( Beg<=Mid ) 
		Query(2*Nod,St,Mid);
	if ( Mid<End )
		Query(2*Nod+1,Mid+1,Dr);
}
